package org.example.myleet.p432;

import java.util.HashMap;

public class AllOne {

    private HashMap<String, LinkNode> keyNodeMap;

    //count小的靠近head，大的靠近tail
    private LinkNode dummyHead;
    private LinkNode dummyTail;

    public AllOne() {
        keyNodeMap = new HashMap<>();
        dummyHead = new LinkNode("head");
        dummyTail = new LinkNode("tail");
        dummyHead.next = dummyTail;
        dummyTail.prev = dummyHead;
    }

    public void inc(String key) {
        LinkNode node = keyNodeMap.get(key);
        if (null == node) {
            //未出现过的key，新建node，并链接到head的next
            node = new LinkNode(key);
            keyNodeMap.put(key, node);
            LinkNode first = dummyHead.next;
            dummyHead.next = node;
            node.prev = dummyHead;
            node.next = first;
            first.prev = node;
        } else {
            //node已存在，+1出现次数
            node.inc();
            //调整node的位置
            balanceInc(node);
        }
    }

    public void balanceInc(LinkNode node) {
        //因为增加了出现次数，因此需要将node往tail方向移动，直到node的head一侧的节点出现次数小于node的出现次数，或node到达链表尾部
        //balanceInc和balanceDec的移动次数理论上不会太多，因为出现次数只变化了1，移动的节点并不会太多
        while (node.count > node.next.count && node.next != dummyTail) {
            LinkNode prev = node.prev;
            LinkNode next = node.next;
            LinkNode nextNext = node.next.next;
            prev.next = next;
            next.prev = prev;
            next.next = node;
            node.prev = next;
            node.next = nextNext;
            nextNext.prev = node;
        }
    }

    public void dec(String key) {
        LinkNode node = keyNodeMap.get(key);
        if (null != node) {
            node.dec();
            if (node.count == 0) {
                LinkNode prev = node.prev;
                LinkNode next = node.next;
                prev.next = next;
                next.prev = prev;
            } else {
                balanceDec(node);
            }
        }
    }

    public void balanceDec(LinkNode node) {
        //因为减少了出现次数，因此需要将node往head方向移动，直到node的tail一侧的节点出现次数大于node的出现次数，或node到达链表头部
        while (node.count < node.prev.count && node.prev != dummyHead) {
            LinkNode prev = node.prev;
            LinkNode next = node.next;
            LinkNode prevPrev = node.prev.prev;
            prevPrev.next = node;
            node.prev = prevPrev;
            node.next = prev;
            prev.prev = node;
            prev.next = next;
            next.prev = prev;
        }
    }

    public String getMaxKey() {
        if (dummyTail.prev == dummyHead) {
            //链表内为空的情况
            return "";
        }
        //拿出靠近tail即count最大的节点
        return dummyTail.prev.key;
    }

    public String getMinKey() {
        if (dummyHead.next == dummyTail) {
            //链表内为空的情况
            return "";
        }
        //拿出靠近head即count最小的节点
        return dummyHead.next.key;
    }

    static class LinkNode {
        //双向链表
        LinkNode prev;
        LinkNode next;
        String key;
        int count;

        public LinkNode(String key) {
            this.key = key;
            count = 1;
        }

        public int inc() {
            return ++count;
        }

        public int dec() {
            return --count;
        }

        public int getCount() {
            return count;
        }

        @Override
        public String toString() {
            final StringBuilder sb = new StringBuilder("LinkNode{");
            sb.append("key='").append(key).append('\'');
            sb.append(", count=").append(count);
            sb.append('}');
            return sb.toString();
        }
    }
}
